package pers.qianyu.month_202102.date_20210214;

import java.util.*;

/**
 * 765. 情侣牵手
 * https://leetcode-cn.com/problems/couples-holding-hands/
 * - 并查集版本
 *
 * @author mizzle rain
 * @date 2021-02-14 10:48
 */
public class MinSwapsCouples {
    private int[] p;

    private int find(int x) {
        if (x != p[x]) {
            p[x] = find(p[x]);
        }
        return p[x];
    }

    public int minSwapsCouples(int[] row) {
        int n = row.length;
        int cnt = n >> 1;
        p = new int[cnt];
        for (int i = 0; i < cnt; i++) p[i] = i;
        for (int i = 0; i < n; i += 2) {
            int x = row[i] / 2, y = row[i + 1] / 2;
            p[find(x)] = find(y);
        }
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < cnt; i++) {
            int root = find(i);
            map.put(root, map.getOrDefault(root, 0) + 1);
        }
        int res = 0;
        for (Integer value : map.values()) {
            res += value - 1;
        }
        return res;
    }
}
